﻿/*****************************************************
 * File:            GraphShortestPath_OLD.cs
 * Description:     Single-Source Shortest Path Problem
 * By:              Ali Khalili (khalili DOT ir AT gmail DOT com)
 * Project:         Automata Learning
 * Namespece		AIDE.Graph
 * Requirements:    
 * Change log:
 *          -Date:  Change
 * To Do:
 *          -Make it compatibale with deligate instead of CostProbPair class!
 *          -
 * License:
 *****************************************************/

using System;
using System.Collections.Generic;
using System.Text;
using SMLib.Base;
using SMLib.Automata.MM;
using SMLib.Automata.Base;


namespace MBT.GraphAlgorithms
{
    /// <summary>
    /// Extended Dijkstra
    /// </summary>
    public class GraphShortestPath<STATETYPE, TRANSITIONTYPE>
        //where TRANSITIONTYPE : ITransition<STATETYPE>
        //where STATETYPE : IState<TRANSITIONTYPE>
    {
        IDiGraph<STATETYPE, TRANSITIONTYPE> ss;
        TransitionCostAssigner<TRANSITIONTYPE> costAssHandler;
        TransitionWeighter<TRANSITIONTYPE> weightHandler;

        List<int> frontiers;
        int[] prevs;
        int[] costs;
        float[] probs;
        bool initialized;

        /// <summary>
        /// By default, we assume that all transitions have the same cost 1
        /// </summary>
        /// <param name="tr"></param>
        /// <returns></returns>
        int costHandDef(TRANSITIONTYPE tr)
        {
            return 1;
        }

        /// <summary>
        /// By default, we assume that all transitions are detetministic!
        /// </summary>
        /// <param name="tr"></param>
        /// <returns></returns>
        float weightHandDef(TRANSITIONTYPE tr)
        {
            return 1.0f;
        }

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="TranSys">the state space</param>
        /// <param name="costAssHandler">the cost assighner (if null, all costs are considered as 1)</param>
        /// <param name="weightHandler">the weight assigner (if null, all transitions are considered to be deterministic)</param>
        public GraphShortestPath(IDiGraph<STATETYPE, TRANSITIONTYPE> DiGraph,
            TransitionCostAssigner<TRANSITIONTYPE> costAssHandler, TransitionWeighter<TRANSITIONTYPE> weightHandler)
        {
            initialized = false;
            this.ss = DiGraph;
            if (costAssHandler != null)
                this.costAssHandler = costAssHandler;
            else
                this.costAssHandler = costHandDef;

            if (weightHandler != null)
                this.weightHandler = weightHandler;
            else
                this.weightHandler = weightHandDef;
        }


        /// <summary>
        /// Compute shortest path of all states from state startIndex
        /// </summary>
        /// <param name="startIndex">the starting state</param>
        public void ComputeShortestPathes(int startIndex = 0)
        {
            initialize(startIndex);

            while (frontiers.Count > 0)
            {
                int fc = frontiers.Count;
                for (int i = 0; i < fc; i++)
                    propagate(i);
                for (int i = 0; i < fc; i++)
                    frontiers.RemoveAt(0);
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="dest"></param>
        /// <returns></returns>
        public List<TRANSITIONTYPE> ShortestPath(int dest)
        {
            List<TRANSITIONTYPE> path = new List<TRANSITIONTYPE>();
            if (dest == 0)
                return path;

            int src = dest;
            while (src != 0)
            {
                STATETYPE st = ss[prevs[src]];
                TRANSITIONTYPE selectedTr = default(TRANSITIONTYPE);
                foreach (TRANSITIONTYPE tr in ss.TransitionsOf(st))
                {
                	if (object.ReferenceEquals(ss.DestinationOf(tr), ss[src]))
                    {
                        selectedTr = tr;
                        break;
                    }
                }
                path.Insert(0, selectedTr);
                // One step back
                src = prevs[src];
            }
            return path;
        }

        /// <summary>
        /// initialize the algorithm
        /// </summary>
        /// <param name="stateIndex">the starting state</param>
        void initialize(int stateIndex)
        {
            if (initialized)
                throw new Exception("This is already initialized!");
            initialized = true;

            prevs = new int[ss.Size];
            costs = new int[ss.Size];
            probs = new float[ss.Size];

            for (int i = 0; i < prevs.Length; i++)
            {
                probs[i] = (i == stateIndex ? 1 : 0);
                costs[i] = (i == stateIndex ? 0 : int.MaxValue);
                prevs[i] = -1;
            }

            frontiers = new List<int>();
            frontiers.Add(stateIndex);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="index"></param>
        void propagate(int index)
        {
            int fc = frontiers.Count;
            for (int i = 0; i < fc; i++)
            {
                int src = frontiers[i];
                foreach (TRANSITIONTYPE t in ss.TransitionsOf(ss[src]))
                {
                	int des = ss.IndexOf( ss.DestinationOf(t));
                    if (costs[des] > (costs[src] + costAssHandler(t))
                        &&
                        probs[des] <= (probs[src] * weightHandler(t)))
                    {
                        if (!frontiers.Contains(des))
                            frontiers.Add(des);
                        costs[des] = (costs[src] + costAssHandler(t));
                        probs[des] = (probs[src] * weightHandler(t));
                        prevs[des] = src;
                    }
                }
            }
        }
    }

    /////////////////////////////////////////////////////////////////////////////////////////////////////////////

    /// <summary>
    ///  Single-Source Shortest Path Problem for a graph: Find the shortest path from specific node to all nodes of the graph
    ///  (Dijkstra's algorithm extended with Probability)
    /// </summary>
    public class GraphShortestPath_OLD<STATETYPE, TRANSITIONTYPE>
        //where TRANSITIONTYPE : ITransition<STATETYPE>
        //where STATETYPE : IState<TRANSITIONTYPE>
    {
        #region Internal Classes

        class CostProbPair
        {
            public float cost;
            public float prob;
            public int prevNode;
            public CostProbPair()
            {
                cost = prob = 0;
                prevNode = -1;
            }
        }

        class defaultCostProbDefinition : ICostProbDefinition<STATETYPE, TRANSITIONTYPE>
        {
            #region ICostProbDefinition Members
            public float CostOfTransition(TRANSITIONTYPE t, STATETYPE s)
            {
                return 1;
            }

            public float ProbOfTransition(TRANSITIONTYPE t, STATETYPE s)
            {
                return 1;
            }
            #endregion
        }

        #endregion

        List<int> frontiers;
        List<CostProbPair> costProbPairs;
        int N;
        IDiGraph<STATETYPE, TRANSITIONTYPE> ss;
        ICostProbDefinition<STATETYPE, TRANSITIONTYPE> definer;


        public GraphShortestPath_OLD(IDiGraph<STATETYPE, TRANSITIONTYPE> myGraph, ICostProbDefinition<STATETYPE, TRANSITIONTYPE> definer)
        {
            if (definer != null)
                this.definer = definer;
            else
                this.definer = new defaultCostProbDefinition();

            N = myGraph.Size;
            ss = myGraph;

            frontiers = new List<int>();
            costProbPairs = new List<CostProbPair>();
        }

        /// <summary>
        /// Initialize the values for a vertix
        /// </summary>
        /// <param name="stateIndex">index of vertix</param>
        void initialize(int stateIndex)
        {
            // Mark the star index as frontier
            frontiers.Clear();
            frontiers.Add(stateIndex);

            // Initialize cost/probability array
            costProbPairs.Clear();
            for (int i = 0; i < N; i++)
            {
                costProbPairs.Add(new CostProbPair());
                if (i == stateIndex)
                {
                    costProbPairs[i].cost = 0;
                    costProbPairs[i].prob = 1;
                }
                else
                {
                    costProbPairs[i].cost = float.MaxValue;
                    costProbPairs[i].prob = 0;
                }
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="startIndex"></param>
        public void ComputeShortestPathes(int startIndex = 0)
        {
            initialize(startIndex);

            while (frontiers.Count > 0)
            {
                int fc = frontiers.Count;
                for (int i = 0; i < fc; i++)
                    propagate(i);
                for (int i = 0; i < fc; i++)
                    frontiers.RemoveAt(0);
            }
        }

        public List<NDGraphTraversalStep<string, int>> ShortestPath(int dest)
        {
            List<NDGraphTraversalStep<string, int>> path = new List<NDGraphTraversalStep<string, int>>();
            if (dest == 0)
                return path;

            int src = dest;
            while (src != 0)
            {
                STATETYPE st = ss[costProbPairs[src].prevNode];
                string transLabel = "";
                foreach (TRANSITIONTYPE tr in ss.TransitionsOf(st))
                {
                	if (object.ReferenceEquals(ss.DestinationOf(tr), ss[src]))
                    {
                        transLabel = tr.ToString();
                        break;
                    }
                }
                path.Insert(0, new NDGraphTraversalStep<string, int>(transLabel, src, false));


                string input = transLabel.Substring(0, transLabel.IndexOf("/"));
                //string cop = transLabel.Substring(transLabel.IndexOf("/") + 1,
                //                    transLabel.Length - transLabel.IndexOf("/") - 1);

                // If it  is a branch point, add all other accepting outputs!
                if (((st as MealyMachine.Mealy_State).ListOfAllNextNodes(new StringSymbol(input)).Count > 1))
                {
                    path[0].MakeItBranch();
                    foreach (MealyMachine.Mealy_Transition t in (st as MealyMachine.Mealy_State).Transitions)
                    {
                        if (t.inLabel.ToString() == input)
                            path[0].OtherAcceptingEdges.Add(t.outLabel.ToString());
                    }
                }

                // One step back
                src = costProbPairs[src].prevNode;
            }
            return path;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="index"></param>
        void propagate(int index)
        {
            int fc = frontiers.Count;
            for (int i = 0; i < fc; i++)
            {
                int src = frontiers[i];
                foreach (TRANSITIONTYPE t in ss.TransitionsOf(ss[src]))
                {
                	int des = ss.IndexOf(ss.DestinationOf(t));
                    if (costProbPairs[des].cost > (costProbPairs[src].cost + definer.CostOfTransition(t, ss[src]))
                        &&
                        costProbPairs[des].prob <= (costProbPairs[src].prob * definer.ProbOfTransition(t, ss[src])))
                    {
                        if (!frontiers.Contains(des))
                            frontiers.Add(des);
                        costProbPairs[des].cost = (costProbPairs[src].cost + definer.CostOfTransition(t, ss[src]));
                        costProbPairs[des].prob = (costProbPairs[src].prob * definer.ProbOfTransition(t, ss[src]));
                        costProbPairs[des].prevNode = src;
                    }
                }
            }
        }
    }

}
